
import java.util.*;
public class Test {
    public String replaceSpace (String s) {
        //建立一个StringBuilder，遇到空格就加入%20,否则就添加字符
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                stringBuilder.append("%20");
            }else{
                stringBuilder.append(s.charAt(i));
            }
        }
        return stringBuilder.toString();
    }
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<>();
        ListNode cur = listNode;
        int count = 0;
        while(cur != null){
            count++;
            array.add(cur.val);
            cur = cur.next;
        }
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i = count - 1; i >= 0; i--){
            ret.add(array.get(i));
        }
        return ret;
    }
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //可以设置每次从顺序表的0下标位置插入，得到的就是逆序
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = listNode;
        while(cur != null){
            list.add(0,cur.val);
            cur = cur.next;
        }
        return list;
    }
    //重建二叉树
    public int preIndex = 0;
    public TreeNode BuildTree(int[] pre, int[] vin, int inBegan, int inEnd){
        if(inBegan > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(pre[preIndex]);
        int rootIndex = funRootIndex(vin, inBegan, inEnd, pre[preIndex]);
        preIndex++;
        root.left = BuildTree(pre, vin, inBegan, rootIndex - 1);
        root.right = BuildTree(pre, vin, rootIndex + 1, inEnd);
        return root;
    }
    public int funRootIndex(int[] vin, int inBegan, int inEnd, int root){
        for(int i = inBegan; i <= inEnd; i++){
            if(vin[i] == root){
                return i;
            }
        }
        return -1;
    }
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        return BuildTree(pre, vin, 0, vin.length - 1);
    }

    //通过中序遍历保存结果顺序表
    ArrayList<TreeLinkNode> list = new ArrayList<>();
    TreeLinkNode ret = null;//待找到的结点
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //先利用next找到整个树的根节点
        TreeLinkNode cur = pNode;
        while(cur.next != null){
            cur = cur.next;
        }
        //建造顺序表
        buildList(cur);
        //找到对应的结点
        int sz = list.size();
        for(int i = 0; i < sz; i++){
            //i + 1 < sz 是为了确保有下一个结点
            if(list.get(i).val == pNode.val && i + 1 < sz){
                return list.get(i + 1);
            }
        }
        return null;
    }
    //建造顺序表
    public void buildList(TreeLinkNode root){
        if(root == null){
            return;
        }
        buildList(root.left);
        list.add(root);
        buildList(root.right);
    }
    //JZ9 用两个栈实现队列
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        if(stack2.isEmpty()){
            stack1.push(node);
        }else{
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            stack1.push(node);
        }
    }

    public int pop() {
        int ret = 0;
        if(!stack2.isEmpty()){
            ret = stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            ret = stack2.pop();
        }
        return ret;
    }

}
